// 组合总和

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class solution_039 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        link(candidates, target, 0, result, new ArrayList<Integer>());
        return result;
    }

    public void link(int[] candidates, int target, int currentValue, List<List<Integer>> result,
            List<Integer> combination) {
        if (target == currentValue) {
            // 当combination变化，result添加的combination也会变化。
            result.add(new ArrayList<Integer>() {
                {
                    addAll(combination);
                }
            });
        }
        if (target > currentValue) {
            for (int i = 0; i < candidates.length && candidates[i] <= (target - currentValue); i++) {
                if (combination.size() == 0 || candidates[i] >= combination.get(combination.size() - 1)) {
                    // 只变化了combination,currentValue没有变化
                    combination.add(candidates[i]);
                    link(candidates, target, currentValue + candidates[i], result, combination);
                    combination.remove(combination.size() - 1);
                }
            }
        }
    }

}

public class Solution039 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backTrace(candidates, result, target, new ArrayList<>(), 0);
        return result;
    }

    private void backTrace(int[] candidates, List<List<Integer>> result, int target, ArrayList<Integer> combination,
            int index) {
        if (index >= candidates.length)
            return;
        if (target == 0){
            result.add(new ArrayList<>(combination));
            return; // 注意这里一定要终止执行，否则会出现重复结果
        }
        // 由于可以选择重复的数，于是能选择0次或多次
        // 1. 选择0次，跳过当前数
        backTrace(candidates, result, target, combination, index + 1);
        // 2. 选择一次当前数，是否再次选择当前数交给递归处理
        if (target >= candidates[index]) {
            combination.add(candidates[index]);
            backTrace(candidates, result, target - candidates[index], combination, index);
            combination.remove(combination.size() - 1);
        }
    }
}